package _binary_search;

/**
 * 74. 搜索二维矩阵
 */
public class No74 {
    public boolean searchMatrix(int[][] matrix, int target) {
        int m = matrix.length;
        int n = matrix[0].length;
        int left0 = 0, right0 = m;
        while (left0 < right0) {
            int mid = left0 + (right0 - left0) / 2;
            if (matrix[mid][n - 1] < target) left0 = mid + 1;
            else right0 = mid;
        }
        if (left0 == m) return false;

        int[] ints = matrix[left0];
        int left1 = 0, right1 = n;
        while (left1 < right1) {
            int mid = left1 + (right1 - left1) / 2;
            if (ints[mid] < target) left1 = mid + 1;
            else right1 = mid;
        }
        return left1 != n && ints[left1] == target;
    }
}
